/*
	    int count = 0,temp_x,temp_y;
		//problema do beco sem saida
		if (i == ind[k].getNumGenes() - 2 && is_in(current_point, dim_map)) {
			if (is_inside(current_point.x - 1, current_point.y, dim_map)
					&& is_inside(current_point.x, current_point.y + 1, dim_map)
					&& is_inside(current_point.x, current_point.y - 1, dim_map))
				if (is_wall(map, current_point.x - 1, current_point.y)
						&& is_wall(map, current_point.x, current_point.y + 1)
						&& is_wall(map, current_point.x, current_point.y - 1)) { //norte - leste - oeste (beco tipo norte)
					fit = fit / PENALTY;
					temp_x = current_point.x; temp_y = current_point.y;
					while(is_wall(map,temp_x,temp_y-1) && is_wall(map,temp_x,temp_y+1)){
						temp_x++; //comeca a descer... ir pro sul no mapa
						count++;
					}
					if(ind[k].getNumGenes() - (count*2) > 2)
						ind[k].DecreaseIndividual(count*2);
					current_point.x = current_point.x + temp_x;
				if (is_inside(current_point.x + 1, current_point.y, dim_map)
					&& is_inside(current_point.x, current_point.y + 1, dim_map)
					&& is_inside(current_point.x, current_point.y - 1, dim_map))
				if (is_wall(map, current_point.x + 1, current_point.y)
						&& is_wall(map, current_point.x, current_point.y + 1)
						&& is_wall(map, current_point.x, current_point.y - 1)) { //sul - leste - oeste (beco tipo sul)
					fit = fit / PENALTY;
					temp_x = current_point.x; temp_y = current_point.y;
					while(is_wall(map,temp_x,temp_y-1) && is_wall(map,temp_x,temp_y+1)){
						temp_x--; //comeca a subir... ir pro norte no mapa
						count++;
					}
					if(ind[k].getNumGenes() - (count*2) > 2)
						ind[k].DecreaseIndividual(count*2);
					current_point.x = current_point.x - temp_x;
				}
			if (is_inside(current_point.x, current_point.y - 1, dim_map)
					&& is_inside(current_point.x - 1, current_point.y, dim_map)
					&& is_inside(current_point.x + 1, current_point.y, dim_map))
				if (is_wall(map, current_point.x, current_point.y - 1)
						&& is_wall(map, current_point.x - 1, current_point.y)
						&& is_wall(map, current_point.x + 1, current_point.y)) { //oeste - norte - sul (beco tipo oeste)
					fit = fit / PENALTY;
					temp_x = current_point.x; temp_y = current_point.y;
					while(is_wall(map,temp_x-1,temp_y) && is_wall(map,temp_x+1,temp_y)){
						temp_y++; //comeca a ir para a direita... ir pro leste no mapa
						count++;
					}
					if(ind[k].getNumGenes() - (count*2) > 2)
						ind[k].DecreaseIndividual(count*2);
					current_point.y = current_point.y + temp_y;

				}
			if (is_inside(current_point.x, current_point.y + 1, dim_map)
					&& is_inside(current_point.x - 1, current_point.y, dim_map)
					&& is_inside(current_point.x + 1, current_point.y, dim_map))
				if (is_wall(map, current_point.x, current_point.y + 1)
						&& is_wall(map, current_point.x - 1, current_point.y)
						&& is_wall(map, current_point.x + 1, current_point.y)) { //leste - norte - sul (beco tipo leste)
					fit = fit / PENALTY;
					temp_x = current_point.x; temp_y = current_point.y;
					while(is_wall(map,temp_x-1,temp_y) && is_wall(map,temp_x+1,temp_y)){
						temp_y--; //comeca a ir para a esquerda... ir pro oeste no mapa
						count++;
					}
					if(ind[k].getNumGenes() - (count*2) > 2)
						ind[k].DecreaseIndividual(count*2);
					current_point.y = current_point.y - temp_y;
				}
		}//fim problema do beco sem saida
*/

//============================================================================
// Name        : Prisons_map.h
// Author      : Andrey Bicalho Santos e Clayson Sandro Celes
// Version     :
// Copyright   : Your copyright notice
// Description : Genetic Algorithm in C++, Ansi-style
//============================================================================

#include <cstdlib>
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <cstring>
#include <math.h>
#include "Individual.h"

#define PENALTY 2
#define BONUS 2
#define TAM_MIN 6

#define TAM_MAX_LINHA 1024

using namespace std;

void pera(){
	string x;
	cin >> x;
}

typedef struct{
	int x,y;
}Point;

string *load_map(FILE *fl, int *num_linhas_mapa);
int count_lines(FILE *fl);
int **get_reduced_map(int **mapa,Point dim_map,Point *dim_reduced_map);
string *build_final_map(int **labirinto,Point dim_labirinto,int **solution_map,Point dim_solution_map);
int **preProcessing(int **mapa,Point dim_map);
int **copy_map(int **map,Point dim_map);
void clone(int **origem,int **destino,Point dim_map);
int **str_map2bin_map(string map[], int num_linhas,Point *dim_labirinto);
int get_number_of_valid_space(int **map, Point dim_map);
bool is_wall(int **map,int x, int y);
bool is_start(int **map,int x, int y);
bool is_end(int **map,int x, int y);
bool is_in(Point current_point, Point dim_map);
bool is_inside(int x,int y,Point dim_map);
Point FindStartPoint(int **map,Point dim_map);
Point FindEndPoint(int **map,Point dim_map);
int count_good_genes(int **solution_map,int **map,Point dim_map);
int count_erros(int **solution_map,int **map,Point dim_map);
void printMapa(int **map,Point dim_map);
int **InsertSolution(Individual *ind,int k,int **map,int dimx, int dimy,Point dim_map);
double euclidian_distance_2D(Point ponto1,Point ponto2);
double fitness_PrisonerProblem(Individual *ind,int k,int n_ind,int **map,Point start,Point end,Point dim_map);
double walk(Individual *ind,int k,int n_ind,int **map,Point current_point,Point dim_map,float fit);
void InitializeIndividualForMazeProblem(Individual *ind,int k,int **labirinto,Point start, Point dim_map);
double fitness_MazeProblem(Individual *ind,int k,int n_ind,int **map,Point start,Point end,Point dim_map,int free_spaces);


//------------------------------------------------------------------------------
string *load_map(FILE *fl, int *num_linhas_mapa){
    string *mapa;
    *num_linhas_mapa = count_lines(fl) - 1;
    int i_linha = 0;
    mapa = new string[*num_linhas_mapa];
    char line_temp[TAM_MAX_LINHA];
    rewind(fl);
    while(fgets(line_temp,TAM_MAX_LINHA,fl) != NULL){
        int z = 0;
        while(line_temp[z] != '\r' && line_temp[z] != '\n'){line_temp[z] = tolower(line_temp[z]); z++;}
        line_temp[z] = '\0';
        mapa[i_linha] = line_temp;
        i_linha++;
    }
    return mapa;
}
//------------------------------------------------------------------------------
//conta a quantidade de linhas do arquivo
int count_lines(FILE *fl){
    int linhas = 1;
    char c;
    rewind(fl);

    do{
         c = fgetc(fl);
         if(c == '\n')
           linhas++;

    }while(c != EOF);
    rewind(fl);
    return linhas;
}
//------------------------------------------------------------------------------
int **get_reduced_map(int **mapa,Point dim_map,Point *dim_reduced_map){
	int new_dimy = (dim_map.y+1)/2, **new_map;

	new_map = new int*[dim_map.x];
	for(int i=0;i < dim_map.x;i++)
		new_map[i] = new int[new_dimy];

	bool sequence3_0 = false;
	int cont;
	for(int i=0;i<dim_map.x;i++){
		cont = 0;
		sequence3_0 = false;
		for(int j=0;j<dim_map.y;j++){
			if(j<(dim_map.y-2)){
				if(mapa[i][j] == 9){
					new_map[i][cont] = 9;
					sequence3_0=false;
					//cont++;
				}
				else if(mapa[i][j] == 1 && mapa[i][j+1] == 1 && mapa[i][j+2] == 1){
					j = j+2;
					new_map[i][cont] = 1;
					//cont++;
				}
				else if(mapa[i][j] == 0 && mapa[i][j+1] == 0 && mapa[i][j+2] == 0 && sequence3_0==false){
					j = j+2;
					new_map[i][cont] = 0;
					sequence3_0 = true;
					//cont++;
				}
				else if(mapa[i][j] == 1){
					sequence3_0=false;
					new_map[i][cont] = 1;
					//cont++;
				}
				else if(mapa[i][j] == 0 && mapa[i][j+1] == 3 && mapa[i][j+2] == 0){
					j = j+2;
					new_map[i][cont] = 3;
					//cont++;
				}
				else if(mapa[i][j] == 0 && mapa[i][j+1] == 5 && mapa[i][j+2] == 0){
					j = j+2;
					new_map[i][cont] = 5;
				}
				/*else if(mapa[i][j] == 3 && mapa[i][j+1] == 0){
					j = j+2;
					new_map[i][cont] = 3;
					//cont++;
				}
				else if(mapa[i][j] == 5 && mapa[i][j+1] == 0){
					j = j+2;
					new_map[i][cont] = 5;
				}*/
				else if(mapa[i][j] == 0 && sequence3_0 == true){
					sequence3_0 = false;
					new_map[i][cont] = 0;
					//printf("\ninvalido!\n");
				}
				cont++;
			}
			else{
				if(mapa[i][j] == 5)
					new_map[i][cont] = 5;
				else if(mapa[i][j] == 3)
					new_map[i][cont] = 3;
				else{

				}
			}
		}
		new_map[i][new_dimy-1] = 9;
	}

	dim_reduced_map->x = dim_map.x;
	dim_reduced_map->y = new_dimy;

	return new_map;
}
//------------------------------------------------------------------------------
string *build_final_map(int **labirinto,Point dim_labirinto,int **solution_map,Point dim_solution_map){

	string *mapa;
	mapa = new string[dim_labirinto.x];

	char *temp;
	temp = new char[dim_labirinto.y+1];

	int cont;
	bool sequence3_0 = false;

	for(int i=0;i<dim_solution_map.x;i++){
		cont = 0;
		sequence3_0 = false;
		for(int j=0;j<dim_solution_map.y;j++){
				if(solution_map[i][j] == 4){
					labirinto[i][cont] = 4;
					labirinto[i][cont+1] = 4;
					labirinto[i][cont+2] = 4;
					cont = cont + 2;
					sequence3_0 = true;
				}
				else if(solution_map[i][j] == 4 && sequence3_0 == true){
					labirinto[i][cont] = 4;
					sequence3_0 = false;
				}

				cont++;
		}

	}


/*
		for(int i=0;i<dim_labirinto.x;i++){
			for(int j=0;i<dim_labirinto.y;i++){
				if(labirinto[i][j] == 9)
					temp[j] = '+';
				else if(labirinto[i][j] == )
			}
		}*/
		printf("\nbuild final map\n");
		printMapa(labirinto,dim_labirinto); pera();

	return mapa;
}
//------------------------------------------------------------------------------
int **preProcessing(int **mapa,Point dim_map){
	for(int i=0;i<dim_map.x;i++)
		for(int j=0;j<dim_map.y;j++)
			if(mapa[i][j] == 9)
				mapa[i][j] = 1;

	return mapa;
}
//------------------------------------------------------------------------------
int **copy_map(int **map,Point dim_map){
	int **copy;
	copy = new int*[dim_map.x];
	for(int i=0;i < dim_map.x;i++)
		copy[i] = new int[dim_map.y];

	for(int i=0;i<dim_map.x;i++)
		for(int j=0;j<dim_map.y;j++)
			copy[i][j] = map[i][j];

	return copy;
}
//------------------------------------------------------------------------------
void clone(int **origem,int **destino,Point dim_map){
	for(int i=0;i<dim_map.x;i++)
		for(int j=0;j<dim_map.y;j++)
			destino[i][j] = origem[i][j];
}
//------------------------------------------------------------------------------
int get_number_of_valid_space(int **map, Point dim_map){
	int valid_space = 0;
	for(int i=0;i<dim_map.x;i++)
		for(int j=0;j<dim_map.y;j++)
			if(map[i][j] == 0)
				valid_space++;

	return valid_space;
}
//------------------------------------------------------------------------------
int **str_map2bin_map(string map[], int num_linhas,Point *dim_labirinto){
	int dimx, dimy;
	dimx = num_linhas;
	dimy = map[0].length(); //assume-se q todas as linhas possuem o mesmo tamanho...
	int **bin_map;
	//cout << dimy << endl; string x; cin >> x;

	//criando matriz dinamicamente
	bin_map = new int*[dimx];
	for(int i=0;i < dimx;i++)
		bin_map[i] = new int[dimy];

	char *temp = new char[dimy+1];

	for(int i=0;i < dimx;i++){
		strcpy(temp,map[i].c_str());
		for(int j=0;j < dimy;j++){
			if(temp[j] == ' ')
				bin_map[i][j] = 0;
			else if(temp[j] == 's')
				bin_map[i][j] = 5;
			else if(temp[j] == 'e')
				bin_map[i][j] = 3;
			else if(temp[j] == '+')
				bin_map[i][j] = 9;
			else
				bin_map[i][j] = 1;
		}
	}

	dim_labirinto->x = dimx;
	dim_labirinto->y = dimy;
	delete[] temp;

	return bin_map;
}
//------------------------------------------------------------------------------
bool is_wall(int **map,int x, int y){
	if(map[x][y] == 1)
			return true;

	return false;
}
//------------------------------------------------------------------------------
bool is_start(int **map,int x, int y){
	if(map[x][y] == 5)
		return true;

	return false;
}
//------------------------------------------------------------------------------
bool is_end(int **map,int x, int y){
	if(map[x][y] == 3)
			return true;

	return false;
}
//------------------------------------------------------------------------------
bool is_in(Point current_point, Point dim_map){
	if((current_point.x >= 0 && current_point.x < dim_map.x) && (current_point.y >= 0 && current_point.y < dim_map.y))
		return true;

	return false;
}
//------------------------------------------------------------------------------
bool is_inside(int x,int y,Point dim_map){
	if((x >= 0 && x < dim_map.x) && (y >= 0 && y < dim_map.y))
		return true;

	return false;
}
//------------------------------------------------------------------------------
Point FindStartPoint(int **map,Point dim_map){
	Point start;
	for(int i=0;i<dim_map.x;i++)
		for(int j=0;j<dim_map.y;j++)
			if(map[i][j] == 5){
				start.x = i;
				start.y = j;
				return start;
			}

	return start;
}
//------------------------------------------------------------------------------
Point FindEndPoint(int **map,Point dim_map){
	Point end;
	for(int i=0;i<dim_map.x;i++)
		for(int j=0;j<dim_map.y;j++)
			if(map[i][j] == 3){
				end.x = i;
				end.y = j;
				return end;
			}

	return end;
}
//------------------------------------------------------------------------------
int count_good_genes(int **solution_map,int **map,Point dim_map){
	int count = 0;
	for(int i=0;i<dim_map.x;i++)
		for(int j=0;j<dim_map.y;j++)
			if(solution_map[i][j] == 4 && map[i][j] == 0)
				count++;

	return count*2;
}
//------------------------------------------------------------------------------
int count_erros(int **solution_map,int **map,Point dim_map){
	int count = 0;
	for(int i=0;i<dim_map.x;i++)
		for(int j=0;j<dim_map.y;j++)
			if(solution_map[i][j] == 4 && map[i][j] == 1)
				count++;

	return count;

}
//------------------------------------------------------------------------------
void printMapa(int **map,Point dim_map){
	printf("\n");
	for(int i=0;i<dim_map.x;i++){
		for(int j=0;j<dim_map.y;j++)
			printf("%d",map[i][j]);
		printf("\n");
	}
}
//------------------------------------------------------------------------------
int **InsertSolution(Individual *ind,int k,int **map,Point dim_map){
	Point current_point = FindStartPoint(map,dim_map);
	int g1,g2;
	//ind[k].printIndividual(); string x; cin >> x;
	for(int i=0;i<ind[k].getNumGenes()-1;i=i+2){
		g1 = ind[k].getGene(i);
		g2 = ind[k].getGene(i+1);
		//11 - norte
		if(g1 == 1 && g2 == 1){
			current_point.x = current_point.x - 1;
			if(is_in(current_point,dim_map)){
				map[current_point.x][current_point.y] = 4;
			}
			else{
				//printf("\nPasso para o Norte, fora do mapa\n");
			}
		}
		//00 - sul
		else if(g1 == 0 && g2 == 0){
			current_point.x = current_point.x + 1;
			if(is_in(current_point,dim_map)){
				map[current_point.x][current_point.y] = 4;
			}
			else{
				//printf("\nPasso para o Sul, fora do mapa\n");
			}
		}
		//01 - ateY,int k_tournament,int k_elitism,int max_min_type);leste
		else if(g1 == 0 && g2 == 1){
			current_point.y = current_point.y + 1;
			if(is_in(current_point,dim_map)){
				map[current_point.x][current_point.y] = 4;
			}
			else{
				//printf("\nPasso para o Leste, fora do mapa\n");
			}
		}
		//10 - oeste
		else if(g1 == 1 && g2 == 0){
			current_point.y = current_point.y - 1;
			if(is_in(current_point,dim_map)){
				map[current_point.x][current_point.y] = 4;
			}
			else{
				//printf("\nPasso para o Oeste, fora do mapa\n");
			}
		}
		else{
			printf("\nInsertion Solution, Error! Invalid Gene: (%d,%d)\n",g1,g2);
		}

	}

	return map;
}
//------------------------------------------------------------------------------
double euclidian_distance_2D(Point ponto1,Point ponto2){
	double distance = 0.0;

	distance = pow((ponto1.x - ponto2.x),2) + pow((ponto1.y - ponto2.y),2);

	return sqrt(distance);
}
//------------------------------------------------------------------------------
void InitializeIndividualForMazeProblem(Individual *ind,int k,int **labirinto,Point start, Point dim_map){
	int g1,g2;
	Point current_point = start;

	for(int i=0;i<ind[k].getNumGenes()-1;i=i+2){
		g1 = ind[k].getGene(i);
		g2 = ind[k].getGene(i+1);
					//WALK
					//11 - norte
					if(g1 == 1 && g2 == 1){
						current_point.x = current_point.x-1;
					}
					//00 - sul
					else if(g1 == 0 && g2 == 0){
						current_point.x = current_point.x+1;
					}
					//01 - leste
					else if(g1 == 0 && g2 == 1){
						current_point.y = current_point.y+1;
					}
					//10 - oeste
					else if(g1 == 1 && g2 == 0){
						current_point.y = current_point.y-1;
					}
					else{
						printf("\nInitializeIndividualForMazeProblem Error, Invalid Gene: (%d,%d) \n",g1,g2); pera();
					}

		if(!is_in(current_point,dim_map)){//fora do mapa
			if(g1 == 1 && g2 == 1){ //norte ---> sul
				ind[k].setGene(i,0);
				ind[k].setGene(i+1,0);
				i = i -2;
			}
			else if(g1 == 0 && g2 == 0){ //sul ---> norte
				ind[k].setGene(i,1);
				ind[k].setGene(i+1,1);
				i = i -2;
			}
			else if(g1 == 0 && g2 == 1){ //leste ---> oeste
				ind[k].setGene(i,1);
				ind[k].setGene(i+1,0);
				i = i -2;
			}
			else if(g1 == 1 && g2 == 0){ //oeste ---> leste
				ind[k].setGene(i,0);
				ind[k].setGene(i+1,1);
				i = i -2;
			}
			else{

			}
		}//fim fora do mapa
		else{
			if(is_end(labirinto,current_point.x,current_point.y) && (ind[k].getNumGenes() - i > 2)){
				//printf("\noi"); pera();
				ind[k].DecreaseIndividual((ind[k].getNumGenes() - i));
				i = ind[k].getNumGenes();
			}
		}


	}//fim for
}
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------

double fitness_MazeProblem(Individual *ind,int k,int n_ind,int **map,Point start,Point end,Point dim_map,int free_space){
	//double fit = ind[k].getNumGenes();
	double fit = 1.0;
	int g1,g2,g1_a = -1,g2_a = -1,passos_errados = 0,increase_value = 2,decrease_value;
	Point current_point = start;
	double distance = 0.0;


		for(int i=0;i<ind[k].getNumGenes()-1;i=i+2){
			g1 = ind[k].getGene(i);
			g2 = ind[k].getGene(i+1);


			if(i >= ind[k].getNumGenes() - 2)
				decrease_value = ind[k].getNumGenes() - i - 2;
			else decrease_value = ind[k].getNumGenes() - i;

			//problema do vai e volta
			if(i >= 2){
				g1_a = ind[k].getGene(i-2); //pega os genes anteriores
				g2_a = ind[k].getGene(i-1);

				if((g1 == 1 && g2 == 1) && (g1_a == 0 && g2_a == 0) ){ // norte-sul
					passos_errados++;
					//fit -= ((fit/ind[k].getNumGenes()) - passos_errados);
					//if((ind[k].getNumGenes() >= TAM_MIN) && (ind[k].getNumGenes() - i > 0)){
						//ind[k].DecreaseIndividual(decrease_value);
						//i = ind[k].getNumGenes() - 2;
						//g1 = ind[k].getGene(i);
						//g2 = ind[k].getGene(i+1);
					//}
					fit = fit/PENALTY;
				}
				else if((g1 == 0 && g2 == 0) && (g1_a == 1 && g2_a == 1)){ //sul-norte
					passos_errados++;
					//if((ind[k].getNumGenes() >= TAM_MIN) && (ind[k].getNumGenes() - i > 0)){
						//ind[k].DecreaseIndividual(decrease_value);
						//i = ind[k].getNumGenes() - 2;
						//g1 = ind[k].getGene(i);
						//g2 = ind[k].getGene(i+1);
					//}
					fit = fit/PENALTY;
				}
				else if((g1 == 0 && g2 == 1) && (g1_a == 1 && g2_a == 0)){ //leste-oeste
					passos_errados++;
					//if((ind[k].getNumGenes() >= TAM_MIN) && (ind[k].getNumGenes() - i > 0)){
						//ind[k].DecreaseIndividual(decrease_value);
						//i = ind[k].getNumGenes() - 2;
						//g1 = ind[k].getGene(i);
						//g2 = ind[k].getGene(i+1);
					//}
					fit = fit/PENALTY;
				}
				else if((g1 == 1 && g2 == 0) && (g1_a == 0 && g2_a == 1)){//oeste-leste
					passos_errados++;
					//if((ind[k].getNumGenes() >= TAM_MIN) && (ind[k].getNumGenes() - i > 0)){
						//ind[k].DecreaseIndividual(decrease_value);
						//i = ind[k].getNumGenes() - 2;
						//g1 = ind[k].getGene(i);
						//g2 = ind[k].getGene(i+1);
					//}
					fit = fit/PENALTY;
				}
				else{
					//faz nada
				}
			}//fim problema do vai e volta

			//problema do beco sem saida
			if (i == ind[k].getNumGenes() - 2 && is_in(current_point, dim_map)) {
				if (is_inside(current_point.x - 1, current_point.y, dim_map)
						&& is_inside(current_point.x, current_point.y + 1, dim_map)
						&& is_inside(current_point.x, current_point.y - 1, dim_map))
					if (is_wall(map, current_point.x - 1, current_point.y)
							&& is_wall(map, current_point.x, current_point.y + 1)
							&& is_wall(map, current_point.x, current_point.y - 1)) { //norte - leste - oeste (beco tipo norte)
						return 0;
					}
					if (is_inside(current_point.x + 1, current_point.y, dim_map)
						&& is_inside(current_point.x, current_point.y + 1, dim_map)
						&& is_inside(current_point.x, current_point.y - 1, dim_map))
					if (is_wall(map, current_point.x + 1, current_point.y)
							&& is_wall(map, current_point.x, current_point.y + 1)
							&& is_wall(map, current_point.x, current_point.y - 1)) { //sul - leste - oeste (beco tipo sul)
						//printf("\nbeco tipo sul");
						return 0;
					}
				if (is_inside(current_point.x, current_point.y - 1, dim_map)
						&& is_inside(current_point.x - 1, current_point.y, dim_map)
						&& is_inside(current_point.x + 1, current_point.y, dim_map))
					if (is_wall(map, current_point.x, current_point.y - 1)
							&& is_wall(map, current_point.x - 1, current_point.y)
							&& is_wall(map, current_point.x + 1, current_point.y)) { //oeste - norte - sul (beco tipo oeste)
						return 0;

					}
				if (is_inside(current_point.x, current_point.y + 1, dim_map)
						&& is_inside(current_point.x - 1, current_point.y, dim_map)
						&& is_inside(current_point.x + 1, current_point.y, dim_map))
					if (is_wall(map, current_point.x, current_point.y + 1)
							&& is_wall(map, current_point.x - 1, current_point.y)
							&& is_wall(map, current_point.x + 1, current_point.y)) { //leste - norte - sul (beco tipo leste)
						return 0;

					}
			}//fim problema do beco sem saida


			g1 = ind[k].getGene(i);
			g2 = ind[k].getGene(i+1);
			//printf("\ni: %d   i+1: %d",i,i+1);

			//WALK
			//11 - norte
			if(g1 == 1 && g2 == 1){
				current_point.x = current_point.x-1;
			}
			//00 - sul
			else if(g1 == 0 && g2 == 0){
				current_point.x = current_point.x+1;
			}
			//01 - leste
			else if(g1 == 0 && g2 == 1){
				current_point.y = current_point.y+1;
			}
			//10 - oeste
			else if(g1 == 1 && g2 == 0){
				current_point.y = current_point.y-1;
			}
			else{
				printf("\nFitness Error, Invalid Gene: (%d,%d) \n",g1,g2); pera();
			}


			if(i >= ind[k].getNumGenes() - 2)
				decrease_value = ind[k].getNumGenes() - i - 2;
			else decrease_value = ind[k].getNumGenes() - i;


			//CHECK
			if(is_in(current_point,dim_map)){//dentro do mapa
				if(is_end(map,current_point.x,current_point.y) && (i == ind[k].getNumGenes() - 2)){ //encontrou fim
					fit = fit*2;
					return fit;
				}
				else if(is_wall(map,current_point.x,current_point.y)){//encontrou uma parede
					passos_errados++;
					if((ind[k].getNumGenes() >= TAM_MIN) && (ind[k].getNumGenes() - i > 0)){
						ind[k].DecreaseIndividual((ind[k].getNumGenes() - i - 2));
						i = ind[k].getNumGenes() - 2;
						g1 = ind[k].getGene(i);
						g2 = ind[k].getGene(i+1);
					}
					fit = fit/(distance+1);
				}
				else{//encontrou lugar valido
					ind[k].IncreaseIndividual(increase_value);
					//fit = fit + BONUS;
				}
			}
			else{ //fora do mapa
				passos_errados++;
				if((ind[k].getNumGenes() >= TAM_MIN) && (ind[k].getNumGenes() - i > 0)){
					ind[k].DecreaseIndividual((ind[k].getNumGenes() - i - 2));
					i = ind[k].getNumGenes() - 2;
					g1 = ind[k].getGene(i);
					g2 = ind[k].getGene(i+1);
				}
				fit = fit/(distance+1);
			}

			if(i == ind[k].getNumGenes() - 2){
				distance = euclidian_distance_2D(current_point,end);
				if(distance <= 0)
					fit = fit;
				else fit = fit/distance;
			}


		} //fim for



		//printf("\n%f\n",fit);
	return fit;
}

//------------------------------------------------------------------------------




//------------------------------------------------------------------------------
/*
 * dica: 1 - razao entre o numero total de genes e numero de colisoes
 *       2 - razao entre o total de passos validos e numero de colisoes
 *       3 - razao entre o numero de passos validos e numero de genes
 *       to achando q essas dicas sao furadas... valem de nada... por isso nem to usando....
 * */
/*double fitness_MazeProblem(Individual *ind,int k,int n_ind,int **map,Point start,Point end,Point dim_map,int free_spaces){
		double fit = 0.0,fit_anterior = ind[k].getFitness();
		int g1,g2,g1_a = -1,g2_a = -1,colisoes = 0,passos_validos = 0;
		Point current_point = start;
		double distance = 0.0;

		for(int i=0;i<ind[k].getNumGenes()-1;i=i+2){
			g1 = ind[k].getGene(i);
			g2 = ind[k].getGene(i+1);


			//problema do vai e volta
			if(i >= 2){
				g1_a = ind[k].getGene(i-2); //pega os genes anteriores
				g2_a = ind[k].getGene(i-1);

				if((g1 == 1 && g2 == 1) && (g1_a == 0 && g2_a == 0) ){ // norte-sul

					fit = fit/PENALTY;
				}
				else if((g1 == 0 && g2 == 0) && (g1_a == 1 && g2_a == 1)){ //sul-norte

					fit = fit/PENALTY;
				}
				else if((g1 == 0 && g2 == 1) && (g1_a == 1 && g2_a == 0)){ //leste-oeste

					fit = fit/PENALTY;
				}
				else if((g1 == 1 && g2 == 0) && (g1_a == 0 && g2_a == 1)){//oeste-leste

					fit = fit/PENALTY;
				}
				else{

				}
			}//fim problema do vai e volta


			g1 = ind[k].getGene(i);
			g2 = ind[k].getGene(i+1);

						//WALK
						//11 - norte
						if(g1 == 1 && g2 == 1){
							current_point.x = current_point.x-1;
						}
						//00 - sul
						else if(g1 == 0 && g2 == 0){
							current_point.x = current_point.x+1;
						}
						//01 - leste
						else if(g1 == 0 && g2 == 1){
							current_point.y = current_point.y+1;
						}
						//10 - oeste
						else if(g1 == 1 && g2 == 0){
							current_point.y = current_point.y-1;
						}
						else{
							printf("\nFitness Error, Invalid Gene: (%d,%d) \n",g1,g2); pera();
						}

			//calculando a distancia
			if(i == ind[k].getNumGenes() - 2)
				distance = euclidian_distance_2D(current_point,end);
			//fim calculando distancia

			if(is_in(current_point,dim_map)){
				if(is_end(map,current_point.x,current_point.y) && (i < ind[k].getNumGenes() - 2)){
					passos_validos++;
					fit += BONUS*(1/(double)((colisoes*PENALTY) + distance + ind[k].getNumGenes()));
					ind[k].DecreaseIndividual((ind[k].getNumGenes() - i));
					i = ind[k].getNumGenes() - 2;
					return fit;
				}
				else if(is_wall(map,current_point.x,current_point.y)){
					colisoes++;
				}
				else{
					passos_validos++;
					//razao = (passos_validos/(double)(ind[k].getNumGenes()/2));
					//printf("\n#Passos validos: %d \t#NumGenes: %d \tNumGenes/2 = %f \tRazao (passos_validos/num_genes) = %f \n",passos_validos,ind[k].getNumGenes(),(double)(ind[k].getNumGenes()/2),razao); pera();
				}
			}
			else{//fora do mapa
				if(g1 == 1 && g2 == 1){ //norte ---> sul
					ind[k].setGene(i,0);
					ind[k].setGene(i+1,0);
					i = i -2;
				}
				else if(g1 == 0 && g2 == 0){ //sul ---> norte
					ind[k].setGene(i,1);
					ind[k].setGene(i+1,1);
					i = i -2;
				}
				else if(g1 == 0 && g2 == 1){ //leste ---> oeste
					ind[k].setGene(i,1);
					ind[k].setGene(i+1,0);
					i = i -2;
				}
				else if(g1 == 1 && g2 == 0){ //oeste ---> leste
					ind[k].setGene(i,0);
					ind[k].setGene(i+1,1);
					i = i -2;
				}
				else{}
			}//fim fora do mapa

			fit += 1/(double)(distance + (colisoes*PENALTY) + ind[k].getNumGenes());
		}//fim for


		if(fit_anterior < fit && is_end(map,current_point.x,current_point.y) && ind[k].getNumGenes() - 2 > 2){
			ind[k].DecreaseIndividual(2);
		}
		else ind[k].IncreaseIndividual(2);


		return fit;
}*/
